// 拓扑排序
#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\6Graph\2_Adjacency_Matrix\Adj_Matrix.h"

void Topological_sort(Adj_Matrix G)
{
    int count = 0; //记录入栈节点个数
    // 1.得到G的各节点入度 degree[]
    int degree[MAX] = {0};
    for (int i = 0; i < G.node_num; i++)
    {
        for (int j = 0; j < G.node_num; j++)
        {
            if (G.M[j][i] != 0 && G.M[j][i] != INFINITY)
            {
                degree[i]++;
            }
        }
    }
    // 2.把入度为0的节点入栈stack
    int stack[MAX];
    int top = -1;
    for (int i = 0; i < G.node_num; i++)
    {
        if (!degree[i])
        {
            stack[++top] = i;
            count++;
        }
    }
    // 3.while(!isempty(stack))
    //   4.输出节点p
    //   5.对于节点p的每一个邻接点w degree[w]--
    //   6.if(degree[w]==0) 入栈
    while (top >= 0)
    {
        int p = stack[top--];
        printf("%3d", G.data[p]);
        for (int i = 0; i < G.node_num; i++)
        {
            if (G.M[p][i] != 0 && G.M[p][i] != INFINITY)
            {
                degree[i]--;
                if (!degree[i])
                {
                    stack[++top] = i;
                    count++;
                }
            }
        }
    }
    // 7.如果有节点没入栈(top<G.node_num) 说明图有环
    if (count < G.node_num)
        printf("ERROR");
}

int main()
{
    /*******************code*******************/
    Adj_Matrix G;
    creat_Topological(G);
    Topological_sort(G);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
